package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code74KthLargestElementInAnArray {

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return -1;
        }
        // 第 k 大, 对应升序数组下标 nums.length - k
        k = nums.length - k;

        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int num = nums[l + (int) (Math.random() * (r - l + 1))];
            int[] pivot = partition(nums, l, r, num);
            if (k < pivot[0]) {
                r = pivot[0] - 1;
            } else if (k > pivot[1]) {
                l = pivot[1] + 1;
            } else {
                return num;
            }
        }
        return -1;
    }

    public int[] partition(int[] nums, int start, int end, int num) {
        if (start == end) {
            return new int[]{start, end};
        }
        int l = start - 1;
        int r = end + 1;
        int index = start;
        while (index < r) {
            if (nums[index] < num) {
                swap(nums, index++, ++l);
            } else if (nums[index] > num) {
                swap(nums, index, --r);
            } else {
                index++;
            }
        }
        return new int[]{++l, --r};
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


    public int findKthLargest1(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return -1;
        }
        int heapSize = nums.length;
        // 构建大根堆
        for (int i = (nums.length - 2 >> 1); i >=0; i--) {
            heapify(nums, i, heapSize);
        }
        // 堆排序
        while (--k > 0) {
            // 弹出顶点到数组最后
            swap(nums, 0, --heapSize);
            // 恢复堆结构
            heapify(nums, 0, heapSize);
        }
        // 堆顶就是第 k 大的数
        return nums[0];
    }

    public void heapify(int[] nums, int index, int size) {
        int left = (index << 1) + 1;
        while (left < size) {
            int largest = left + 1 < size && nums[left + 1] > nums[left] ? left + 1 : left;
            largest = nums[largest] > nums[index] ? largest : index;

            if (largest == index) {
                break;
            }
            swap(nums, largest, index);
            index = largest;
            left = (index << 1) + 1;
        }
    }
}
